package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Description 完成所有工作的最短时间
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.8
 */

public class T1723 {
    public static void main(String[] args) {
        T1723 t1723 = new T1723();

        int[] jobs = {1, 2, 4, 7, 8};
        int k = 2;

        System.out.println(t1723.minimumTimeRequired02(jobs, k));

    }

    /**
     * 暴力解法
     */
    public int minimumTimeRequired01(int[] jobs, int k) {
        int limit = Arrays.stream(jobs).sum();
        jobs = Arrays.stream(jobs).boxed().sorted(Comparator.reverseOrder()).mapToInt(i -> i).toArray();
        while (limit > 0) {//这里可以进行优化，采用二分，每次满足时减半而不是减1，当不满足时新增一半
            if (enough(jobs, limit, k)) {
                limit--;
            } else {
                break;
            }
        }
        limit++;

        return limit;
    }

    public boolean enough(int[] jobs, int limit, int k) {
        int[] workload = new int[k];
        for (int i = 0; i < jobs.length; i++) {
            int j = 0;
            for (; j < k; j++) {
                if (workload[j] + jobs[i] <= limit) {
                    workload[j] += jobs[i];
                    break;
                }
            }
            if (j == k) {
                return false;
            }
        }
        return true;

    }


    /**
     * 二分剪枝
     *
     * @param jobs
     * @param k
     * @return
     */
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int low = 0, high = jobs.length - 1;
        while (low < high) {
            int temp = jobs[low];
            jobs[low] = jobs[high];
            jobs[high] = temp;
            low++;
            high--;
        }
        int l = jobs[0], r = Arrays.stream(jobs).sum();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public boolean check(int[] jobs, int k, int limit) {
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, 0, limit);
    }

    public boolean backtrack(int[] jobs, int[] workloads, int i, int limit) {
        if (i >= jobs.length) {
            return true;
        }
        int cur = jobs[i];
        for (int j = 0; j < workloads.length; ++j) {
            if (workloads[j] + cur <= limit) {
                workloads[j] += cur;
                if (backtrack(jobs, workloads, i + 1, limit)) {
                    return true;
                }
                workloads[j] -= cur;
            }
            // 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
            // 或者当前工作恰能使该工人的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (workloads[j] == 0 || workloads[j] + cur == limit) {
                break;
            }
        }
        return false;
    }


    /**
     * 小机灵解法 错误
     * [5,5,4,4,4]
     * 2
     */
    public int minimumTimeRequired02(int[] jobs, int k) {
        int limit = Arrays.stream(jobs).sum();
        jobs = Arrays.stream(jobs).boxed().sorted(Comparator.reverseOrder()).mapToInt(i -> i).toArray();

        int[] workloads = new int[k];
        int i = 0;
        while (i < jobs.length) {
            int tmp = Integer.MAX_VALUE;
            int tmpIndex = -1;
            for (int j = 0; j < k; j++) {
                if (workloads[j] + jobs[i] < tmp) {
                    tmp = workloads[j] + jobs[i];
                    tmpIndex = j;
                }
            }
            workloads[tmpIndex] += jobs[i];
            i++;
        }
        return Arrays.stream(workloads).max().getAsInt();
    }

}
